package com.lzp.leetcode.dp.simple;

/**
 * 零钱兑换
 *
 * @author lzp
 * @date 2020/7/5
 */
public class D1_LC322_CoinChange {
    /**
     * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
     * 如果没有任何一种硬币组合能组成总金额，返回 -1。
     */
    public int coinChange(int[] coins, int amount) {
        // 硬币种类数
        int n = coins.length;

        // f[0], f[1], ..., f[amount]
        int[] f = new int[amount + 1];

        // 初始条件
        f[0] = 0;

        int i, k;
        for (i = 1; i <= amount; i++) {
            f[i] = Integer.MAX_VALUE;
            for (k = 0; k < n; k++) {
                // 边界
                if (i >= coins[k] && f[i - coins[k]] != Integer.MAX_VALUE) {
                    // 取所有硬币情况的最小值
                    f[i] = Math.min(f[i], f[i - coins[k]] + 1);
                }
            }
        }

        // 输出结果
        return f[amount] == Integer.MAX_VALUE ? -1 : f[amount];
    }
}
